package 剑指Offer.medium;

public class 二叉搜索树与双向链表 {
    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }

    ;

    class Solution {
        Node pre, head;

        public Node treeToDoublyList(Node root) {
            if (root == null) {
                return null;
            }
            dfs(root);
            //首尾相连
            head.left = pre;
            pre.right = head;
            return head;
        }

        private void dfs(Node cur) {
            if (cur == null) {
                return;
            }
            //遍历左子树
            dfs(cur.left);

            //处理当前层业务，建立连接
            if (pre != null) {
                pre.right = cur;
            } else {
                //head仅仅用来保存头结点，仅在左递归最深层调用一次
                head = cur;
            }
            cur.left = pre;
            pre = cur;

            //遍历右子树
            dfs(cur.right);
        }
    }
}
